package com.LeeCode;

import java.util.TreeMap;

/**
 * 将区间分为最少组数
 */

public class Code2406 {
    public static void main(String[] args) {

    }

    public int minGroups(int[][] intervals) {
        // 使用 TreeMap 自动按坐标排序
        TreeMap<Integer, Integer> diff = new TreeMap<>();

        for (int[] interval : intervals) {
            int start = interval[0];
            int end = interval[1];
            diff.merge(start, 1, Integer::sum);      // 开始：+1
            diff.merge(end + 1, -1, Integer::sum);   // 结束后：-1
        }

        int maxOverlap = 0;
        int current = 0;

        // 按坐标顺序遍历所有事件点
        for (int delta : diff.values()) {
            current += delta;
            maxOverlap = Math.max(maxOverlap, current);
        }

        return maxOverlap;
    }
}
